package com.leetcode.algorithm.y22.m09.w2;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * 
 * https://leetcode.cn/problems/3sum-closest/
 * 
 * @author jie.deng
 *
 */
class Question0016Solution01 {

	public int threeSumClosest(int[] nums, int target) {
		Arrays.sort(nums);
		int len = nums.length;
		int minDiff = nums[0] + nums[1] + nums[2] - target;
		for (int i = 0; i < len; i++) {
			int a1 = nums[i];
			int left = i + 1;
			int right = len - 1;
			while (left < right) {
				int diff = a1 + nums[left] + nums[right] - target;
				if (diff > 0) {
					if (diff < Math.abs(minDiff)) {
						minDiff = diff;
						if (minDiff == 0) {
							return target;
						}
					}
					right--;
				} else {
					if (-diff < Math.abs(minDiff)) {
						minDiff = diff;
						if (minDiff == 0) {
							return target;
						}
					}
					left++;
				}
			}
		}
		return target + minDiff;
	}

}